package LearnDataStructure.a_线性结构.例题;

import java.util.EmptyStackException;
import java.util.Iterator;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-04 15:01
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.a_线性结构.例题
 */
/*
要求，求最小值min的时间复杂度是O(1)
构造满足上述要求的栈

 */
public class h_构造最短时间找min的栈<T extends Comparable<T>> extends MyLinkedListDouble<T> implements MyStackAPI<T> {

    public static void main(String[] args) {
        h_构造最短时间找min的栈<Integer> test = new h_构造最短时间找min的栈<>();
        test.push(3);
        test.push(6);
        test.push(38);
        test.push(1);
        test.push(7);
        System.out.println(test.min());

        test.pop();
        System.out.println(test.min());
        test.pop();
        System.out.println(test.min());
        test.pop();
        System.out.println(test.min());
        test.pop();
        System.out.println(test.min());
        test.pop();
        System.out.println(test.min());
    }

    @Override
    public void push(T element) {
        super.add(element);


        if (helper.empty()) {
            helper.push(element);
        } else {
            T peek = helper.peek();
            if (element.compareTo(helper.tail.pre.data) < 0) {
                helper.push(element);
            } else {
                helper.push(peek);
            }
        }
    }

    @Override
    public T pop() {
        if (super.size <= 0) {
            throw new EmptyStackException();
        }
        StackNode<T> top = super.tail.pre;
        T res = top.data;
        top.pre.next = super.tail;
        super.tail.pre = top.pre;
        top.pre = null;
        top.next = null;
        super.size--;
        helper.pop();
        return res;
    }

    @Override
    public boolean empty() {
        return getSize() == 0;
    }

    @Override
    public int getSize() {
        return super.size;
    }

    @Override
    public T peek() {
        return super.tail.pre.data;
    }

    private MyStackList<T> helper = new MyStackList<T>();//不能用“h_构造最短时间找min的栈”本身作为helper，会导致无限循环

    /**
     * 当元素不重复的前提下
     * 这个方法还可以优化，使其更节约空间
     * helper只保存当前压入是的最小值
     *          在原栈弹出时，比较弹出值与helper.peek()，如果弹出值<=helper.peek(),那么helper才进行pop()
     * @return
     */
    public T min() {
        return helper.peek();
    }
}

class StackNode<T> {
    T data;
    StackNode<T> pre;
    StackNode<T> next;

    public StackNode(T data) {
        this.data = data;
    }

    public StackNode() {
    }

    @Override
    public String toString() {
        return "StackNode{" +
                "data=" + data +
                ", pre=" + pre +
                ", next=" + next +
                '}';
    }
}

interface MyStackAPI<T> {
    /**
     * 压栈
     * @param element
     */
    void push(T element);

    /**
     * 弹栈
     * @return
     */
    T pop();

    /**
     * 判断是否空栈
     * @return
     */
    boolean empty();

    /**
     * 返回当前栈内元素个数
     * @return
     */
    int getSize();

    /**
     * 查看栈顶元素，不弹出
     * @return
     */
    T peek();
}

class MyStackList<T> extends MyLinkedListDouble<T> implements MyStackAPI<T> {
    @Override
    public void push(T element) {
        super.add(element);
    }

    @Override
    public T pop() {
        if (super.size <= 0) {
            throw new EmptyStackException();
        }
        StackNode<T> top = super.tail.pre;
        T res = top.data;
        top.pre.next = super.tail;
        super.tail.pre = top.pre;
        top.pre = null;
        top.next = null;
        super.size--;
        return res;
    }

    @Override
    public boolean empty() {
        return getSize() == 0;
    }

    @Override
    public int getSize() {
        return super.size;
    }

    @Override
    public T peek() {
        return super.tail.pre.data;
    }

    @Override
    public String toString() {
        return super.toString();
    }
}

class MyLinkedListDouble<T> implements MyList<T> {
    StackNode<T> head = new StackNode<T>();
    StackNode<T> tail = new StackNode<T>();
    StackNode<T> now = head;
    int size = 0;

    public MyLinkedListDouble() {
        head.next = tail;
        tail.pre = head;
    }

    @Override
    public void add(T element) {
        StackNode<T> newNode = new StackNode<T>(element);//新节点

        tail.pre.next = newNode;//尾部前一个节点A 的 后继是 新节点
        newNode.next = tail;//新节点的后继是尾部
        newNode.pre = tail.pre;//新节点的前驱是A
        tail.pre = newNode;//尾部的前驱是新节点

        size++;
    }

    @Override
    public void delete(T element) {
        if (head.next == tail) {
            return;
        }
        StackNode<T> p = head.next;
        while (p != tail) {
            if (p.data.equals(element)) {
                p.pre.next = p.next;
                p.next.pre = p.pre;
                p.pre = null;
                p.next = null;
                size--;
                break;
            }
            p = p.next;
        }
    }

    @Override
    public void delete(int index) {
        if (index < 0 || index >= size || head.next == tail) {
            return;
        }
        int i = 0;
        StackNode<T> p = head.next;
        while (p != tail) {
            if (i == index) {
                p.pre.next = p.next;
                p.next.pre = p.pre;
                p.pre = null;
                p.next = null;
                size--;
                break;
            }
            p = p.next;
            i++;
        }
    }

    @Override
    public void update(int index, T newElement) {
        if (index < 0 || index >= size || head.next == tail) {
            return;
        }
        int i = 0;
        StackNode<T> p = head.next;
        while (p != tail) {
            if (i == index) {
                p.data = newElement;
                break;
            }
            p = p.next;
            i++;
        }
    }

    @Override
    public boolean contains(T target) {
        if (head.next != tail) {
            StackNode<T> p = head.next;
            while (p != tail) {
                if (p.data.equals(target)) {
                    return true;
                }
                p = p.next;
            }
        }
        return false;
    }

    @Override
    public T AtElement(int index) {
        if (index < 0 || index >= size || head.next == tail) {
            return null;
        }
        int i = 0;
        StackNode<T> p = head.next;
        while (p != tail) {
            if (i == index) {
                return p.data;
            }
            p = p.next;
            i++;
        }
        return null;
    }

    @Override
    public int indexOf(T element) {
        if (head.next != tail) {
            int i = 0;
            StackNode<T> p = head.next;
            while (p != tail) {
                if (p.data.equals(element)) {
                    return i;
                }
                p = p.next;
                i++;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("[");
        StackNode<T> p = head.next;
        while (p != tail) {
            stringBuilder.append(p.data);
            if (p.next != tail) {
                stringBuilder.append(" , ");
            }
            p = p.next;
        }
        stringBuilder.append("] size = " + size);
        return stringBuilder.toString();
    }

    /**
     * 此元素后面是否还有元素
     * @return
     */
    @Override
    public boolean hasNext() {
        return now.next != tail;
    }

    /**
     * 返回从head开始的，下一个元素A，到tail前一个元素B为止
     * @return
     */
    @Override
    public T next() {
        StackNode<T> next = now.next;
        now = now.next;
        return next.data;
    }
}

interface MyList<T> extends Iterator<T> {
    /**
     * 新增
     * @param element
     */
    void add(T element);

    /**
     * 删除指定内容的元素
     * @param element
     */
    void delete(T element);

    /**
     * 删除指定下标的元素
     * @param index
     */
    void delete(int index);

    /**
     * 修改指定索引的元素
     * @param index
     * @param newElement
     */
    void update(int index,T newElement);

    /**
     * 容器中是否含有target这个内容的元素
     * @param target
     * @return
     */
    boolean contains(T target);

    /**
     * 返回指定索引的元素
     * @param index
     * @return
     */
    T AtElement(int index);

    /**
     * 返回指定元素的索引
     * @param element
     * @return
     */
    int indexOf(T element);
}